package Tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 530.二叉搜索树的最小绝对差
 * 给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
 * 差值是一个正数，其数值等于两值之差的绝对值。
 */
public class getMinimumDifference {
    /**
     * 一刷
     * 利用二叉搜索树的特点，中序遍历是一个递增的数组
     */
    public int getMinimumDifference(TreeNode root) {

        List<Integer> list = new ArrayList<>();
        order(root, list);
        int min = Integer.MAX_VALUE;
        for (int i = 1; i < list.size(); i++) {
            min = Math.min(min, Math.abs(list.get(i) - list.get(i - 1)));
        }

        return min;

    }

    public static List<Integer> order(TreeNode root, List<Integer> list) {
        if(root == null) return new ArrayList<>();
        order(root.left, list);
        list.add(root.val);
        order(root.right, list);
        return list;
    }

    /**
     * 二刷
     */
    class Solution {
        TreeNode pre;// 记录上一个遍历的结点
        int result = Integer.MAX_VALUE;
        public int getMinimumDifference(TreeNode root) {
            if(root==null)return 0;
            traversal(root);
            return result;
        }
        public void traversal(TreeNode root){
            if(root==null)return;
            //左
            traversal(root.left);
            //中
            if(pre!=null){
                result = Math.min(result,root.val-pre.val);
            }
            pre = root;
            //右
            traversal(root.right);
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(6);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);

    }
}
